6.2 Dynamic Routing Overview  
  6.2.6 Link-state routing protocol features  
The second basic algorithm used for routing is the link-state algorithm. Link-state algorithms are also known as Dijkstras algorithm or as SPF (shortest path first) algorithms. Link-state routing algorithms maintain a complex database of topology information. The distance vector algorithm has nonspecific information about distant networks and no knowledge of distant routers. A link-state routing algorithm maintains full knowledge of distant routers and how they interconnect.

Link-state routing uses:

  • Link-state advertisements (LSAs) – A link-state advertisement (LSA) is a small packet of routing information that is sent between routers.
  • Topological database – A topological database is a collection of information gathered from LSAs.
  • SPF algorithm – The shortest path first (SPF) algorithm is a calculation performed on the database resulting in the SPF tree.
  • Routing tables – A list of the known paths and interfaces.

Network discovery processes for link state routing
LSAs are exchanged between routers starting with directly connected networks for which they have direct information. Each router in parallel with the others constructs a topological database consisting of all the exchanged LSAs.

The SPF algorithm computes network reachability. The router constructs this logical topology as a tree, with itself as the root, consisting of all possible paths to each network in the link-state protocol internetwork. It then sorts these paths Shortest Path First (SPF). The router lists the best paths and the interfaces to these destination networks in the routing table. It also maintains other databases of topology elements and status details.

The router that first becomes aware of a link-state topology change forwards the information so that all other routers can use it for updates. This involves sending common routing information to all routers in the internetwork. To achieve convergence, each router keeps track of its neighbor routers, the router name, interface status, and the cost of the link to the neighbor. The router constructs an LSA packet that lists this information along with new neighbors, changes in link costs, and links that are no longer valid. The LSA packet is then sent out so that all other routers receive it.

When the router receives an LSA, the database is updated with the most recent information and computes a map of the internetwork using the accumulated data and calculates the shortest path to other networks using the SPF algorithm. Each time an LSA packet causes a change to the link-state database, SPF recalculates the best paths and updates the routing table.

Link-state concerns:

  • Processor overhead
  • Memory requirements
  • Bandwidth Consumption

Routers running link-state protocols require more memory and perform more processing than distance vector routing protocols. Routers must have sufficient memory to be able to hold all the information from the various databases, the topology tree, and the routing table. Initial link-state packet flooding consumes bandwidth. During the initial discovery process, all routers using link-state routing protocols send LSA packets to all other routers. This action floods the internetwork and temporarily reduces bandwidth available for routed traffic carrying user data. After this initial flooding, link-state routing protocols generally require only minimal bandwidth to send infrequent or event triggered LSA packets reflecting topology changes.

 

Web Links

Routing Protocols - Link State

http://www.firewall.cx/i ndex.php?c=link_state